O(log N)
対数時間
入力のサイズが2倍になっても、計算時間が定数だけ増えることを意味する
具体例
sortされた1024要素を持つリストから特定の値を探す
中央を見て、それより大きいか小さいか判断
対象が521個に絞られる
その半分の中央を見て、それより大きいか小さいか判断
対象が256個に絞られる
...というのを繰り返す
とやると、最大で10ステップで求められる
$ log_2{1024}= log_2{2^{10}} = 10
回
例
二分探索